package com.leetcode.字符串;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xaxi62/
 * 来源：力扣（LeetCode）SparseArray
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class 分割回文串1 {

	public List<List<String>> partition(String s) {
		return partitionHelper(s, 0);
	}

	private List<List<String>> partitionHelper(String s, int start) {
		//递归出口，空字符串
		if (start == s.length()) {
			List<String> list = new ArrayList<>();
			List<List<String>> ans = new ArrayList<>();
			ans.add(list);
			return ans;
		}
		List<List<String>> ans = new ArrayList<>();
		for (int i = start; i < s.length(); i++) {
			//当前切割后是回文串才考虑
			if (isPalindrome(s.substring(start, i + 1))) {
				String left = s.substring(start, i + 1);
				//遍历后边字符串的所有结果，将当前的字符串加到头部
				for (List<String> l : partitionHelper(s, i + 1)) {
					l.add(0, left);
					ans.add(l);
				}
			}

		}
		return ans;
	}

	private boolean isPalindrome(String s) {
		int i = 0;
		int j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) != s.charAt(j)) {
				return false;
			}
			i++;
			j--;
		}
		return true;
	}

	@Test
	public void test() {
		System.out.println(partition("aabcdcba"));
	}
}
